
# def isSquare(num):
#     return num==pow(num,0.5)**2


# def isSquare(num):
#     low=1
#     high=num
#     while low < high:
#         mid=(low+high)//2
#         power=mid**2
#         print(power,num)
#         if power>num: high=mid-1
#         elif power<num: low=mid+1
#         else: return True
#     return False

# def isPower(num):
#     if num <1: return False
#     i=1
#     while i <= num:
#         if i == num: return True
#         i <<= 1
#     return False

# def isPower(num):
#     if num <1: return False
#     return not num&(num-1)

# def randB():
#     while True:
#         x = randA()
#         if x<= B:
#             return x

# def randB():
#     while True:
#         x = A*(randA()-1)+randA()
#         if x<= B*(A//B):
#             return x%B+1

# def zeroCount(n):
#     count = 0
#     while n > 0:
#         n = n//5
#         count += n
#     return count

# print(zeroCount(1024))

# def intToBinary(n):
#     hexNum = 8*8 #占位符
#     bit = ''
#     for i in range(hexNum):
#         b = n>>i
#         c = b%2
#         bit += str(c)
#     return bit

# def pgcd(a, b):
#     return a if not b else pgcd(b, a%b)

# import math
# print(math.factorial(6))

# print(pow(899,5433,97))

# def fastExp(a, b, q):
#     assert a >= 0 and b >= 0 and q >= 1
#     p = 0 # 只用于记录
#     p2 = 1 # 2^p
#     ap2 = a%q # a^(2^p)
#     result = 1
#     while b > 0:
#         if p2 & b > 0: #b由a^(2^p)拆分而来
#             b -= p2
#             result = (result * ap2) % q
#         p += 1
#         p2 *= 2
#         ap2 = (ap2 * ap2) % q
#     return result

# print(eval('3*2+4/2-9'))

# def calculate(s: str):
#     #处理中序表达式
#     sign_list = {"+", "-", "*", "/", "(", ")"}
#     lst1 = []
#     now = ""
#     for ch in s:
#         if ch in sign_list:
#             if now:
#                 lst1.append(now)
#                 now = ""
#             lst1.append(ch)
#         elif ch.isnumeric():
#             now += ch
#     if now:
#         lst1.append(now)
#     # 将中缀表达式转换为后缀表达式
#     lst2 = []
#     stack = []
#     for e in lst1:
#         if e.isnumeric():
#             lst2.append(e)
#         else:
#             if e == ")":
#                 while stack and stack[-1] != "(":
#                     lst2.append(stack.pop())
#                 stack.pop()
#             elif e == "*" or e == "/":
#                 while stack and stack[-1] in {"*", "/"}:
#                     lst2.append(stack.pop())
#                 stack.append(e)
#             elif e == "+" or e == "-":
#                 while stack and stack[-1] in {"+", "-", "*", "/"}:
#                     lst2.append(stack.pop())
#                 stack.append(e)
#             else:  # e == "("
#                 stack.append(e)
#     while stack:
#         lst2.append(stack.pop())
#     # 后缀表达式计算结果
#     stack = []
#     for e in lst2:
#         if e.isnumeric():
#             stack.append(int(e))
#         else:
#             b = stack.pop()
#             a = stack.pop()
#             if e == "+":
#                 stack.append(a + b)
#             elif e == "-":
#                 stack.append(a - b)
#             elif e == "*":
#                 stack.append(a * b)
#             else:  # e = "/"
#                 stack.append(a / b)
#     return stack[0]

# print(calculate('3*2+4/2-9'))
